package study1;

import org.w3c.dom.Node;

public class GetNodes {
    static class TreeNode {
        public char val;         // 节点存储的字符值
        public TreeNode left;    // 左子节点引用
        public TreeNode right;   // 右子节点引用

        public TreeNode(char val) {
            this.val = val;      // 构造函数初始化节点值
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        return A;
    }


    /**
     * 核心逻辑：通过先序遍历（根 → 左 → 右）逐个累加节点。
     * 特点：
        使用成员变量 nodeSize 存储结果（需调用后访问该变量）。
        递归前重置计数器（避免多次调用时结果叠加）。
        时间复杂度：O(N)（每个节点访问一次）。
     * 缺点：依赖成员变量，多次调用需手动重置计数器。
     **/
    public int nodeSize; // 成员变量计数器
    public void getNodeSize1(TreeNode root) {
        nodeSize = 0;          // 重置计数器
        if (root == null) return;
        nodeSize++;            // 当前节点计数+1
        getNodeSize1(root.left);  // 递归遍历左子树
        getNodeSize1(root.right); // 递归遍历右子树
    }


    /**
     * 核心逻辑：采用分治法（后序遍历）。
     * 特点：
        纯递归实现，直接返回结果（无需成员变量）。
        逻辑简洁，无副作用。
     * 递归过程：
        空树 → 返回 0。
        非空树 → 返回 左子树节点数 + 右子树节点数 + 1。
     **/
    public int getNodeSize2(TreeNode root) {
        if (root == null) return 0; // 空树返回0
        // 递归公式：总节点数 = 左子树节点数 + 右子树节点数 + 1（当前节点）
        return getNodeSize2(root.left) + getNodeSize2(root.right) + 1;
    }
}
